class Solution {
public:
    unordered_map<string,int> ump;
    vector<int> f,size;
    
    int find(int x){
        return x == f[x] ? x : find(f[x]);
    }
    void Union(int u,int v){
        int x = find(u);
        int y = find(v);
        if(x == y) return;
        if(x > y){
            swap(x,y);
        }
        
        f[y] = x;
        size[x] += size[y];
    }
    
    string record(int x,string& s){
        int n = s.size();
        int flag = 0;
        int ret = 0;
        for(int i = 0;i < n;i++){
            if(s[i] == '('){
                flag = i;
            }
            if(s[i] >= '0' && s[i] <= '9'){
                ret = ret * 10 + s[i] - '0';
            }
        }
        
        string ss = string(s.begin(),s.begin()+flag);
        ump[ss] = x;
        if(!size[x]){
            size[x] = ret;
        } 
    
        return ss;
    }
    
    vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) {
        
        sort(names.begin(),names.end());
        
        int n = names.size();
        f.resize(n);
        size.resize(n);
        
        for(int i = 0;i < n;i++){
            f[i] = i;
        }
        for(int i = 0;i < n;i++){
            record(i,names[i]);
        }
        
        int m = synonyms.size();
        for(auto& s : synonyms){
            string a,b;
            int flag = 0;
            for(int i = 0;i < s.size();i++){
                if(s[i] == ','){
                    flag = i;
                    break;
                }
            }
            a = string(s.begin()+1,s.begin()+flag);
            b = string(s.begin()+flag+1,s.end()-1);
            if(!ump.count(a)){
                int len = f.size();
                f.push_back(len);
                size.push_back(0);
                ump[a] = len;
            }
            if(!ump.count(b)){
                int len = f.size();
                f.push_back(len);
                size.push_back(0);
                ump[b] = len;
            }
            Union(ump[a],ump[b]);
        }
        
        vector<string> ret;
        for(int i = 0;i < n;i++){
            if(f[i] == i){
                string s = record(i,names[i]);
                s += "(";
                s += to_string(size[i]);
                s += ")";
                ret.push_back(s);
            }
        }
        return ret;
        
    }
};
